4 sum [Two pointer, Hash]

Time: O(N^3); Space: O(1); medium

Given an array nums of N integers, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notes:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a <= b <= c <= d)

• The solution set must not contain duplicate quadruplets.

Example 1:

Input: nums = [1, 0, -1, 0, -2, 2], target = 0.

Output:

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

class Solution1(object):
    """
    Two pointer solution. (1356ms)
    """
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        for i in range(len(nums) - 3):
            if i and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 2):
                if j != i + 1 and nums[j] == nums[j - 1]:
                    continue
                sum = target - nums[i] - nums[j]
                left, right = j + 1, len(nums) - 1
                while left < right:
                    if nums[left] + nums[right] == sum:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        right -= 1
                        left += 1
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1
                    elif nums[left] + nums[right] > sum:
                        right -= 1
                    else:
                        left += 1
        return res

s = Solution1()
nums = [1, 0, -1, 0, -2, 2]
target = 0
# assert s.fourSum(nums, target) == [[-1,  0, 0, 1], [-2, -1, 1, 2], [-2,  0, 0, 2]]
print(s.fourSum(nums, target))

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

import collections

class Solution2(object):
    """
    Hash solution. (224ms)
    Time: O(N^2 * p)
    Space: O(N^2 * p)
    """
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
        for i in range(0, len(nums) - 1):
            for j in range(i + 1, len(nums)):
                is_duplicated = False
                for [x, y] in lookup[nums[i] + nums[j]]:
                    if nums[x] == nums[i]:
                        is_duplicated = True
                        break
                if not is_duplicated:
                    lookup[nums[i] + nums[j]].append([i, j])
        ans = {}
        for c in range(2, len(nums)):
            for d in range(c+1, len(nums)):
                if target - nums[c] - nums[d] in lookup:
                    for [a, b] in lookup[target - nums[c] - nums[d]]:
                        if b < c:
                            quad = [nums[a], nums[b], nums[c], nums[d]]
                            quad_hash = " ".join(str(quad))
                            if quad_hash not in ans:
                                ans[quad_hash] = True
                                result.append(quad)
        return result

s = Solution2()
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(s.fourSum(nums, target))

[[-1, 0, 0, 1], [-2, 0, 0, 2], [-2, -1, 1, 2]]

class Solution3(object):
    """
    Time: O(N^2 * p) ~ O(N^4)
    Space: O(N^2)
    """
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
        for i in range(0, len(nums) - 1):
            for j in range(i + 1, len(nums)):
                lookup[nums[i] + nums[j]].append([i, j])

        for i in lookup.keys():
            if target - i in lookup:
                for x in lookup[i]:
                    for y in lookup[target -i]:
                        [a, b], [c, d] = x, y
                        if a is not c and a is not d and b is not c and b is not d:
                            quad = sorted([nums[a], nums[b], nums[c], nums[d]])
                            if quad not in result:
                                result.append(quad)
        return sorted(result)

s = Solution3()
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(s.fourSum(nums, target))

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

See also:

https://leetcode.com/problems/4sum

https://www.lintcode.com/problem/4sum